#pragma once
#include<iostream>
#include<vector>
#include<functional>
#include<queue>
#include<climits>
#include<stack>
#include<list>
using namespace std;

class MinStack {
public:
    stack<int> m1;
    stack<int> m2;
    MinStack() {
        m2.push(INT_MAX);
    }

    void push(int val) {
        m1.push(val);
        m2.push(min(val, m2.top()));
    }

    void pop() {
        m1.pop();
        m2.pop();
    }

    int top() {
        return m1.top();
    }
    int getMin() {
        return m2.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

//class Solution {
//public:
//    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
//        stack<int> p1;
//        int i = 0, j = 0;
//        while (j < popV.size()&& i < pushV.size()) {
//           while (i < pushV.size() && j < popV.size() && pushV[i] == popV[j]) {
//                ++i, ++j; 
//           }
//            while (!p1.empty() && j < popV.size() && p1.top() == popV[j]) {
//                p1.pop();
//                j++;
//            }
//            while (i < pushV.size() && pushV[i] != popV[j]) {
//                p1.push(pushV[i]);
//                i++;
//            }
//        }
//        return p1.empty();
//    }
//};

//namespace bit
//{
//    template<class T, class Con = deque<T>>
//    class stack
//    {
//    public:
//        stack() {}
//        void push(const T& x) {
//            _c.push_back(x);
//        }
//        void pop() {
//            _c.pop_back();
//        }
//        T& top() {
//            return _c.back();
//        }
//        const T& top()const {
//            return _c.back();
//        }
//        size_t size()const {
//            return _c.size();
//        }
//        bool empty()const {
//            return _c.empty();
//        }
//    private:
//        Con _c;
//    };
//    template<class T, class Con = deque<T>>
//    class queue
//    {
//    public:
//        queue(){}
//        void push(const T& x) {
//            _c.push_back(x);
//        }
//        void pop() {
//            _c.pop_front();
//        }
//        T& back() {
//           return  _c.back();
//        }
//        const T& back()const {
//            return _c.back();
//        }
//        T& front() {
//            return _c.front();
//        }
//        const T& front()const {
//            return _c.front();
//        }
//        size_t size()const {
//            return _c.size();
//        }
//        bool empty()const{
//            return _c.empty();
//        }
//    private:
//        Con _c;
//    };
//};
//
//class Solution {
//public:
//    int findKthLargest(vector<int>& nums, int k) {
//        priority_queue<int,vector<int>,less<int>> n(nums.begin(),nums.end());
//        for (int i = 0; i < k-1; i++) {
//            n.pop();
//        }
//        return n.top();
//    }
//};

namespace bit{
    template <class T, class Container = vector<T>, class Compare = less<T> >
    class priority_queue{
    public:
        priority_queue() {};
        void AdjustDwonwards(T parent) {
            int child = parent * 2 + 1;
            while (child < c.size()) {
                if (child + 1 < c.size() && comp(c[child], c[child + 1])) {
                    child = child + 1;
                }
                if (comp(c[parent], c[child])) {
                    swap(c[child], c[parent]);
                    parent = child;
                    child = parent * 2 + 1;
                }
                else {
                    break;
                }
            }
        }
        //0
        //1 2
        //3 4  5 6
        void AdjustUpwards(T child) {
            int parent = (child - 1) / 2;
            while (child >0) {
                if (child + 1 < c.size() && comp(c[child], c[child + 1])) {
                    child = child + 1;
                }
                if (comp(c[parent], c[child])) {
                    swap(c[child], c[parent]);
                    child = parent;
                    parent = (child - 1) / 2;
                }
                else {
                    break;
                }
            }
        }

        template <class InputIterator>
        priority_queue(InputIterator first, InputIterator last) {
            for (InputIterator it = first; it != last;) {
                c.push_back(*it);
                it++;
            }
            for (int i = c.size() / 2 - 1; i >= 0; i--) {
                AdjustDwonwards(i);
            }
        }
        bool empty() const {
            return c.empty();
        }
        size_t size() const {
            return c.size();
        }
        const T& top() const {
            return c[0];
        }
        void push(const T& x) {
            c.push_back(x);
            AdjustUpwards(c.size() - 1);
        }
        void pop() {
            swap(c[0], c[c.size() - 1]);
            c.pop_back();
            AdjustDwonwards(0);
        }
    private:
        Container c;
        Compare comp;
    };
};